<?php

class SimulatedAnnealing {
	private $fileName;
	private $data;
	private $trial;
	private $temperatureStart;
	private $temperatureEnding;
	private $coolingFactor;
	private $globalDistances;			// Acts as global buffer; distances between cities
	
	public function __construct($temperatureStart = 150, $coolingFactor = 0.95, $temperatureEnding = 0.01) {
		$this->data					= array();
		$this->trial 				= array();
		$this->temperatureStart 	= $temperatureStart;
		$this->temperatureEnding 	= $temperatureEnding;
		$this->coolingFactor 		= $coolingFactor;
	}
	
	public function run() {
		
		$this->annealing();
	}
	
	public function annealing($solution = null) {
		$temperature = $this->temperatureStart;
		$temperatureEnding = $this->temperatureEnding;
		$cycle = 0;
		$sameCount = 0;
		if ($solution != null) {
			$currentBest = $solution;
		} else {
			$currentBest = $this->nearestNeighbor();
		}
		
		$bestSolution = $currentBest;

		$costCurrentBest = $this->length($currentBest);
		$costBest = $costCurrentBest;
	
		$currentSolution = $currentBest;
		$costCurrent = $costCurrentBest;
		
		$overAllStart = microtime(true);
		while ($temperature > $temperatureEnding && $sameCount != 50) {
			$start = microtime(true);
			
			$n = count($this->data);
			for($i = 0; $i < $n; $i++) {
				
				$a = rand(1, $n-1);
				$b = rand(1, $n-1);
				
				$distance = $this->getDistance($a, $a+1) + $this->getDistance($b, $b+1) - $this->getDistance($a, $b) - $this->getDistance($a+1, $b+1);
				
				if ($this->anneal($distance, $temperature)) {
					if ($b <= $a) {
						$temp = $a;
						$a = $b;
						$b = $temp;
					}
					
					while ($b > $a) {
						$switched = array();
						$newSolution = $currentSolution;
						
						$temp = $newSolution[$a];
						$newSolution[$a] = $newSolution[$b];
						$newSolution[$b] = $temp;
						
						foreach($newSolution as $idx) {
							$switched[$idx] = $idx;
						}
						
						$currentSolution = $switched;
						
						$costCurrent = $this->length($currentSolution);
						if ($costCurrent < $costCurrentBest) {
							$currentBest = $currentSolution;
							$costCurrentBest = $costCurrent;
						}
						
						$b--;
						$a++;
					}
				}
				
			}
			
			if ($costBest > $costCurrentBest) {
				echo 'aa';			
				die();
				$sameCount = 0;
			} else {
				$sameCount++;
			}
			$temperature = $temperature * $this->coolingFactor;
			$cycle++;
			
			echo 'Solution: ' . $this->length($bestSolution) . ' Time: ' . (microtime(true) - $start) . ' s' . PHP_EOL;
		}
	
		echo 'Solution: ' . $this->length($bestSolution) .  'Whole time: ' . (microtime(true) - $overAllStart) . ' s' . PHP_EOL;
		
		return $bestSolution;
	}
	
	public function anneal($distance, $delta) {
		
		if ($delta < 0.0001) {
			
			if ($distance > 0) {
				
				return true;
			} else {
				
				return false;
			}
			
		}
		
		$exp = exp(($distance / $delta));
		$randomNumber = $this->getRandomFloatingPointNumber(0, 1);

		if ($delta > 0 || $exp <= $randomNumber) {
			
			return true;
		}
		
		return false;
	}
	
	public function length($solution = null) {
		$code = sha1(implode('-', $solution));
		
		if (isset($this->globalDistances[$code])) {
		
			return $this->globalDistances[$code];
		}
		
		if ($solution == null) {
			$solution = $this->trial;
		}

		$cost = 0;
		$first = current(array_keys($solution));
		$from = $first;
		foreach ($solution as $to) {
			if ($first == $to) {
				continue;
			}

			$distance = $this->getDistance($from, $to);

			$from = $to;
			$cost += $distance;
		}

		$distance = $this->getDistance($from, $first);
		
		$cost += $distance;
		
		$code2 = sha1(strrev(implode('-', $solution)));
		$this->globalDistances[$code] = $cost;
		$this->globalDistances[$code2] = $cost;
		
		return $cost;
	}
	
	private function getDistance($a, $b) {
		
		return $this->d($this->data[$a], $this->data[$b]);
	}
	
	private function nearestNeighbor() {
		// Start from random city
// 		$start = rand(1, count($this->data));
		$start = 1;
		$unvisited = $this->data;
		$visited = array();
		$node = $start;
		while (count($unvisited) > 0) {
			$visited[$node] = $node;
			$nearest = $this->getNearest($node, $unvisited);
			unset($unvisited[$node]);
			$node = $nearest;
		}
	
		return $visited;
	}
	
	private function getNearest($source, $unvisited) {
		$sourceCoords = $unvisited[$source];
		$distances = array();
		foreach ($unvisited as $node => $coords) {
			if ($node != $source) {
				$distances[$node] = $this->d($sourceCoords, $coords);
			}
		}
	
		asort($distances);
	
		return current(array_keys($distances));;
	}
	
	/* Euclidean Distance */
	private function d($a, $b) {
		list($x1, $y1) = $a;
		list($x2, $y2) = $b;
	
		return sqrt(pow($x1 - $x2, 2) + pow($y1 - $y2, 2));
	}
	
	/* Helper */
	private function shuffleAssoc($array) {
		$shuffled = array();
		$keys = array_keys($array);
		shuffle($keys);
	
		foreach($keys as $key) {
			$shuffled[$key] = $array[$key];
		}
	
		return $shuffled;
	}
	
	public function read($fileName) {
		$this->fileName = $fileName;
		$file = fopen($fileName . '.txt', 'r');
		$header = fgets($file);
	
		$count = 1;
		while (!feof($file)) {
			$line = fgets($file);
			$row = preg_split('/\s+/', $line);
	
			if (count($row) < 2) {
				break;
			}
	
			$this->data[$count] = array($row[0], $row[1]);
			$count++;
		}
	
		fclose($file);
	}
	
	private function getRandomFloatingPointNumber($min, $max) {
	
		return $min + mt_rand() / mt_getrandmax() * ($max - $min);
	}
	
}

$fileName = 'TSP_100';

$sa = new SimulatedAnnealing();
$sa->read($fileName);
$sa->run();